1. Technical Field
The present invention relates in general to digital circuitry and, in particular, to a queue within a digital circuit. Still more particularly, the present invention relates to an improved queue design having distributed multiplexing logic.
2. Description of the Related Art
As illustrated in FIG. 1, one conventional realization of a first in, first out (FIFO) queue 10 within a field programmable gate array (FPGA) includes two or more entry latches 12, one for each entry in FIFO queue 10. Each entry latch 12 is implemented with a D-latch having an n-bit data input (D), an enable input (E), a clock input (CLK), and an n-bit data output (Q). To form FIFO queue 10, entry latches 12 are cascaded, with the output of each entry latch 12 except the one forming the bottom entry being connected to the data input of the latch forming the subsequent entry and the data input of the latch forming the top entry receiving the n-bit Data_in value. The data output (Q) of each of entry latches 12 is also connected to a respective input of multiplexer 14, which selects as an output value the n-bit input value specified by the select signal generated by mux control 16 in response to global Read and Write control signals. The n-bit output of multiplexer 14 is in turn connected to the data input of an output latch 18, which latches in input values and latches out an n-bit data_out value in response to the clock input (CLK).
During operation, when mux control 16 senses that the Read control signal is asserted, mux control 16 generates a select signal that specifies the mux input corresponding to the oldest occupied entry in FIFO queue 10. During the clock cycle in which the Read control signal is asserted, the input value present at the selected mux input is passed to output latch 18, which latches in the input value. Then, during the next clock cycle, output latch 18 outputs the n-bit Data_out value.
Conversely, when the Write control signal is asserted, the Data_in value is latched into the entry latch 12 forming the top entry in FIFO queue 10. Because the Write control signal is connected to the enable inputs of all entry latches 12, each other entry latch 12 latches the value held by the preceding entry latch 12 during a write. The value, if any, held by the entry latch 12 forming the bottom entry in the queue is latched out and discarded (unless the Read control signal is also asserted).
The present invention includes a recognition that the conventional FIFO queue design for FPGAs depicted in FIG. 1 suffers from a number of deficiencies. For example, the operation of output latch 18 introduces a cycle of latency in the output data path, as discussed above. In addition, as queue depth increases, multiplexer 14 becomes large and operates more slowly, which introduces additional latency in the output data path. Furthermore, the delay associated with the interconnect connecting entry latches 12 and multiplexer 14 can introduce significant latency in the operation of FIFO queue 10. It would therefore be desirable to provide an improved queue design for that addresses these and other deficiencies of the conventional FIFO queue design shown in FIG. 1.